/*
// Definition for a QuadTree node.
class Node {
public:
    bool val;
    bool isLeaf;
    Node* topLeft;
    Node* topRight;
    Node* bottomLeft;
    Node* bottomRight;
    
    Node() {
        val = false;
        isLeaf = false;
        topLeft = NULL;
        topRight = NULL;
        bottomLeft = NULL;
        bottomRight = NULL;
    }
    
    Node(bool _val, bool _isLeaf) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = NULL;
        topRight = NULL;
        bottomLeft = NULL;
        bottomRight = NULL;
    }
    
    Node(bool _val, bool _isLeaf, Node* _topLeft, Node* _topRight, Node* _bottomLeft, Node* _bottomRight) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = _topLeft;
        topRight = _topRight;
        bottomLeft = _bottomLeft;
        bottomRight = _bottomRight;
    }
};
*/

class Solution {
    Node *dfs(vector<vector<int>>& grid, int x0, int y0, int x1, int y1)
    {
        for(int i = x0; i < x1; i++)
        {
            for(int j = y0; j < y1; j++)
            {
                if(grid[i][j] != grid[x0][y0])
                {
                    return new Node(1, false, 
                    dfs(grid, x0, y0, (x0 + x1) / 2, (y0 + y1) / 2),
                    dfs(grid, x0, (y0 + y1) / 2, (x0 + x1) / 2, y1),
                    dfs(grid, (x0 + x1) / 2, y0, x1, (y0 + y1) / 2),
                    dfs(grid, (x0 + x1) / 2, (y0 + y1) / 2, x1, y1));
                }
            }
        }
        // 全部都相等，说明是叶子节点
        return new Node(grid[x0][y0], true);
    }
public:
    Node* construct(vector<vector<int>>& grid) {
        // 传遍历范围进去
        return dfs(grid, 0, 0, grid.size(), grid.size());
    }
};